using System;

namespace LeetCode {
    public class wildcard {
        public bool IsMatch (string s, string p) {
            bool[, ] dp = new bool[p.Length + 1, s.Length + 1];
            dp[0, 0] = true;
            for (int i = 1; i <= p.Length; i++) {
                dp[i, 0] = dp[i - 1, 0] && p[i - 1] == '*';
                for (int j = 1; j <= s.Length; j++) {
                    if (p[i - 1] == '*')
                        dp[i, j] = dp[i, j - 1] || dp[i - 1, j];
                    else {
                        dp[i, j] = dp[i - 1, j - 1] && ((s[j - 1] == p[i - 1]) || p[i - 1] == '?');
                    }
                }
            }
            return dp[p.Length,s.Length];
        }
    }
}